import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class II81 {
    public static void main(String[] args) {
        int[] candidates = {2,3,5};
        int target = 8;
        System.out.println(combinationSum(candidates,target));
    }
    //dfs
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(candidates);
        dfs1(ans,new LinkedList<>(),candidates,target,0,0);
        return ans;
    }
    public static void dfs1(List<List<Integer>> ans,List<Integer> list,int[] nums,int target,int sum,int start){
        if(sum>target) return;
        if(sum==target){
            ans.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i<nums.length;i++){
            sum+=nums[i];
            if(sum>target) break;
            list.add(nums[i]);
            dfs1(ans, list, nums, target, sum,i);
            sum-=nums[i];
            list.remove(list.size()-1);
        }
    }

}
